#include "graphsupporttest/TestGraphGenerate.h"

#include <memory>
#include <stdlib.h>
#include <ext/hash_map>

#include "boosttestsupport.h"

#include "accumulsupport/AccumulSupport.h"

namespace stdext
{
	using namespace __gnu_cxx;
}

#include "graphsupport/graph/FacilitiesGraph.h"
#include "graphsupport/graph/operation/GenBipartLinkNear.h"
#include "graphsupport/graph/operation/CompoundGraphOperation.h"
#include "graphsupport/graph/operation/MakeSymmOperation.h"
#include "graphsupport/graph/operation/AddChpExpWeightsOperation.h"
#include "graphsupport/graph/operation/TriangleInequalityCloseOperation.h"
#include "graphsupport/graph/operation/GeneratePricesOperation.h"

#include "graphsupport/graph/generate/DefaultGraphGenerator.h"

#include "graphsupport/solve/facilitylocation/PrimDualSolvContext.h"

int getEdgesCount( Graph & gr, Graph::AdjCoefType fromWeight = -1e30, Graph::AdjCoefType toWeight = 1e30 )
{
	int result = 0;
	int n = gr.getVertexCount();
	Graph::AdjMatrixType adjMatrix = gr.getAdjacentMatrixArr();

	for ( int i = 0; i < n; i++ )
	{
		for ( int j = 0; j < n; j++ )
		{
			if ( gr.existsEdge( i, j ) && adjMatrix[i][j] >= fromWeight && adjMatrix[i][j] <= toWeight )
			{
				result++;
			}
		}
	}

	return result;
}

void TestGraphOperation()
{
	Graph gr( 100 );
	int totalEdges0 = getEdgesCount( gr );
	BOOST_CHECK( totalEdges0 == 0 );

	IGraphOperationPtr operation( new GenBipartLinkNear() );
	IOperationSettings genSettings( gr.getVertexCount() );
	genSettings.neighborsBeg = 5;
	genSettings.neighborsRange = 1;
	operation->applyTo( gr, genSettings );
	int totalEdges1 = getEdgesCount( gr );
	BOOST_CHECK( totalEdges1 > totalEdges0 );
	BOOST_CHECK_LT( std::abs( gr.getVertexCount() * 5 - totalEdges1 ), 30 ); // average ~~ 5

	Graph gr1( 100 );
	BOOST_CHECK( getEdgesCount( gr1 ) == 0 );
	operation->applyTo( gr1, genSettings );
	int totalEdges2 = getEdgesCount( gr1 );
	BOOST_CHECK( totalEdges1 != totalEdges2 );
}

int getNeighborsCount( Graph & gr, int vert )
{
	int result = 0;
	for ( int i = 0; i < gr.getVertexCount(); i++ )
	{
		if ( gr.existsEdge( vert, i ) )
		{
			result++;
		}
	}
	return result;
}

void TestGenNearNeighborDiffer()
{
	Graph gr( 1000 );
	int totalEdges0 = getEdgesCount( gr );
	BOOST_CHECK( totalEdges0 == 0 );

	std::auto_ptr< IGraphOperation > operation( new GenBipartLinkNear() );
	IOperationSettings genSettings( gr.getVertexCount() );
	genSettings.neighborsBeg = 30;
	genSettings.neighborsRange = 10;
	operation->applyTo( gr, genSettings );

	stdext::hash_map< int, int > registredNeighborCount;

	// test default is 0
	{
		BOOST_CHECK_EQUAL( registredNeighborCount[1234], 0 );
		registredNeighborCount[1234]++;
		BOOST_CHECK_EQUAL( registredNeighborCount[1234], 1 );
		registredNeighborCount = stdext::hash_map< int, int >();
	}

	BOOST_CHECK_EQUAL( registredNeighborCount.size(), 0 );

	for ( int i = 0; i < gr.getVertexCount(); i++ )
	{
		int neighborsCount = getNeighborsCount( gr, i );
		registredNeighborCount[neighborsCount]++;
	}

	BOOST_CHECK_GT( registredNeighborCount.size(), 10 );
}

class Color
{
public:
	static const int COL_UNDEF = 0;

	static const int COL_B = 2;
	static const int COL_W = 3;

	static int invCol( int color )
	{
		return color ^ 1;
	}
};

void dfsDetColor( Graph & gr, int vert, int * colors )
{
	if ( colors[vert] == Color::COL_UNDEF )
	{
		colors[vert] = Color::COL_W;
	}

	for ( int i = 0; i < gr.getVertexCount(); i++ )
	{
		if ( gr.existsEdge( vert, i ) && colors[i] == Color::COL_UNDEF )
		{
			colors[i] = Color::invCol( colors[vert] );
			dfsDetColor( gr, i, colors );
		}
	}
}

void TestBipartite()
{
	int n = 100;
	std::vector< int > colors( n );

	BiGraph gr( n / 3, n - n / 3 );

	GenBipartLinkNear genOp;

	IOperationSettings genSettings( n );
	genSettings.neighborsBeg = 9;
	genSettings.neighborsRange = 1;
	genOp.applyTo( gr, genSettings );

	int detColorGroupsCount = 0;
	for ( int i = 0; i < n; i++ )
	{
		if ( colors[i] == Color::COL_UNDEF )
		{
			dfsDetColor( gr, i, & colors[0] );
			detColorGroupsCount++;
		}
	}
	BOOST_CHECK_EQUAL( detColorGroupsCount, 1 );

	int colorBCount = 0, colorWCount = 0;
	for ( int i = 0; i < n; i++ )
	{
		if ( colors[i] == Color::COL_B )
		{
			colorBCount++;
		} else
		{
			colorWCount++;
		}

		for ( int j = 0; j < n; j++ )
		{
			if ( gr.existsEdge( i, j ) )
			{
				BOOST_CHECK_NE( colors[i], colors[j] );
				if ( colors[i] == colors[j] )
				{
					std::cout << "color[" << i << "] = " << colors[i]
					   << " clolor[" << j << "] = " << colors[j] << "\n";
					return;
				}
			}
		}
	}

	if ( colorBCount > colorWCount )
	{
		int tmp = colorBCount;
		colorBCount = colorWCount;
		colorWCount = tmp;
	}
	if ( detColorGroupsCount == 1 )
	{
		BOOST_CHECK_EQUAL( colorBCount, n / 3 );
		BOOST_CHECK_EQUAL( colorWCount, n - n / 3 );
	}
}

void findEdges( Graph & gr, std::vector< std::pair< int, int > > & edges )
{
	int n = gr.getVertexCount();

	for ( int i = 0; i < n; i++ )
	{
		for ( int j = 0; j < n; j++ )
		{
			if ( gr.existsEdge( i, j ) )
			{
				edges.push_back( std::pair< int, int >( i, j ) );
			}
		}
	}
}

class AppToBuf
{
public:
	AppToBuf( std::stringstream & buf )
		: buf( buf )
	{
	}

	void operator () ( std::pair< int, int > & item )
	{
		buf << item.first << " -> " << item.second << "; ";
	}

private:
	std::stringstream & buf;
};

std::string edgesToString( std::vector< std::pair< int, int > > & edges )
{
	std::stringstream buf;
	AppToBuf appToBuf( buf );
	std::for_each( edges.begin(), edges.end(), appToBuf );
	return buf.str();
}

class MockOperation : public IGraphOperation
{
public:
	MockOperation( int from, int to )
		: from( from )
		, to( to )
	{
	}

	virtual void applyTo( Graph & graph, IOperationSettings & genSettings )
	{
		graph.getAdjacentMatrixArr()[from][to] = 1.0;
	}

private:
	int from;
	int to;
};

void TestCompoundOperation()
{
	int n = 100;

	Graph gr( n );

	CompoundGraphOperation * compOp = new CompoundGraphOperation();
	IGraphOperationPtr theOp( compOp );

	IOperationSettings genSettings( n );
	theOp->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );
	BOOST_CHECK_EQUAL( 0, getEdgesCount( gr ) );

	compOp->addSubOperation( IGraphOperationPtr( new MockOperation( 12, 34 ) ) );
	compOp->addSubOperation( IGraphOperationPtr( new MockOperation( 67, 89 ) ) );

	theOp->applyTo( gr, genSettings );

	BOOST_CHECK( gr.existsEdge( 12, 34 ) );
	BOOST_CHECK( gr.existsEdge( 67, 89 ) );

	std::vector< std::pair< int, int > > edges;
	findEdges( gr, edges );

	BOOST_CHECK_EQUAL( std::string( "12 -> 34; 67 -> 89; " ), edgesToString( edges ) );
}

void TestMakeSymmOperation()
{
	Graph gr( 10 );
	Graph::AdjMatrixType adjMatrix = gr.getAdjacentMatrixArr();

	adjMatrix[0][1] = 1;
	adjMatrix[2][3] = 1;
	adjMatrix[4][5] = 1;

	BOOST_CHECK( !gr.existsEdge( 5, 4 ) );
	BOOST_CHECK( !gr.existsEdge( 3, 2 ) );
	BOOST_CHECK( !gr.existsEdge( 1, 0 ) );

	MakeSymmOperation makeSymmOperation;
	IGraphOperation * theOp = & makeSymmOperation;

	theOp->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );

	BOOST_CHECK( gr.existsEdge( 5, 4 ) );
	BOOST_CHECK( gr.existsEdge( 3, 2 ) );
	BOOST_CHECK( gr.existsEdge( 1, 0 ) );
}

int findPair( Graph & gr, int vert, Graph::AdjCoefType cheap, int cheapRange )
{
	int n = gr.getVertexCount();
	Graph::AdjMatrixType adjMatr = gr.getAdjacentMatrixArr();
	Graph::AdjCoefType EPS = 1e-5;

	int result = -1;
	for ( int i = 0; i < n; i++ )
	{
		if ( std::abs( adjMatr[vert][i] - cheap ) < cheapRange )
		{
			if ( result > -1 )
			{
				return -1;
			}
			result = i;
		}
	}

	return result;
}

void TestAddChpExpWeightsOperation()
{
//	IGNORE( "TestAddChpExpWeightsOperation" );
	Graph::AdjCoefType EPS = 1e-5;

	int n = 200;
	int firstBipart = n / 2;
	int secondBipart = n - firstBipart;
	BiGraph gr( firstBipart, secondBipart );
	Graph::AdjCoefType cheap = 100;
	int cheapRange = 20;
	Graph::AdjCoefType expensive = 700;
	int expensiveRange = 20;
	int aveNeighbors = 5;

	BOOST_CHECK_EQUAL( 0, getEdgesCount( gr ) );

	GenBipartLinkNear gbplOp;
	AddChpExpWeightsOperation acewOp;

	IGraphOperation * theOp = & acewOp;
	IOperationSettings genSettings( n );
	genSettings.neighborsBeg = aveNeighbors;
	genSettings.neighborsRange = 1;
	genSettings.cheapBeg = 100;
	genSettings.expensiveBeg = 700;
	theOp->applyTo( gr, genSettings );
	BOOST_CHECK_EQUAL( 0, getEdgesCount( gr ) );

	gbplOp.applyTo( gr, genSettings );
	BOOST_CHECK_GT( getEdgesCount( gr, 0.0, 1.1 ), 10 );
	acewOp.applyTo( gr, genSettings );
	BOOST_CHECK_EQUAL( 0, getEdgesCount( gr, 0.0, 1.1 ) );

	Graph::AdjMatrixType adjMatr = gr.getAdjacentMatrixArr();

	for ( int i = 0; i < firstBipart; i++ )
	{
		int expensiveCount = 0;
		int cheapCount = 0;

		for ( int j = 0; j < firstBipart; j++ )
		{
			BOOST_CHECK( !gr.existsEdge( i, j ) );
			if ( gr.existsEdge( i, j ) )
			{
				std::cout << "\nexists edge: " << i << " -> " << j;
				return;
			}
		}

		for ( int j = firstBipart; j < n; j++ )
		{
			BOOST_CHECK_GE( j >= firstBipart, gr.existsEdge( i, j ) );
			if ( j < firstBipart && gr.existsEdge( i, j ) )
			{
				std::cout << "i = " << i << " j = " << j << " exist = "
					<< gr.existsEdge( i, j ) << "\n";
			}
			assert( ( j >= firstBipart ) >= gr.existsEdge( i, j ) );

			Graph::AdjCoefType cost = adjMatr[i][j];
			if ( std::abs( cost - expensive ) < expensiveRange )
			{
				expensiveCount++;
			}
			if ( std::abs( cost - cheap ) < cheapRange )
			{
				cheapCount++;
			}
		}

		BOOST_CHECK_GT( expensiveCount, 0 );
		BOOST_CHECK_LT( expensiveCount, aveNeighbors * 2 );
		BOOST_CHECK_EQUAL( 1, cheapCount );
		if ( expensiveCount == 0 || expensiveCount >= aveNeighbors * 2 || cheapCount != 1 )
		{
			std::cout << "i = " << i << " expensiveCount = "
				<< expensiveCount << " cheapCoun = " << cheapCount << "\n";
			BOOST_CHECK( false );
			return;
		}
	}

	std::vector< int > secBiPrt2pairsCount( firstBipart + secondBipart );
	for ( int i = 0; i < firstBipart; i++ )
	{
		int pair = findPair( gr, i, cheap, cheapRange );
		secBiPrt2pairsCount[pair]++;
	}

	int conflictPairsCount = 0;
	for ( int i = firstBipart; i < firstBipart + secondBipart; i++ )
	{
		int prsCount = secBiPrt2pairsCount[i];
		BOOST_CHECK_LE( prsCount, n / 50 );// probabilistic evaluation
		if ( prsCount > 1 )
		{
			conflictPairsCount++;
		}
	}
	BOOST_CHECK_LT( conflictPairsCount, n / 6 ); // 1/6 -- probabilistic evaluation; may be broken is random-algorithm changed
}

void TestAddChpExpErases_2ndBP_to_1stBP_edges()
{
//	IGNORE( "TestAddChpExpErases_2ndBP_to_1stBP_edges" );
	Graph::AdjCoefType EPS = 1e-5;

	int n = 10;
	Graph gr( n );

	Graph::AdjMatrixType adjMatrix = gr.getAdjacentMatrixArr();
	adjMatrix[3][7] = 1;
	adjMatrix[7][2] = 1;

	BOOST_CHECK( gr.existsEdge( 7, 2 ) );
	BOOST_CHECK_EQUAL( 2, getEdgesCount( gr ) );

	AddChpExpWeightsOperation acewOp;
	acewOp.applyTo( gr, IOperationSettings::EMPTY_SETTINGS );
	BOOST_CHECK_EQUAL( 2, getEdgesCount( gr ) );
//	BOOST_CHECK( !gr.existsEdge( 7, 2 ) );
	BOOST_CHECK( gr.existsEdge( 3, 7 ) );
}

void TestDefaultGenerator()
{
//	IGNORE( "TestDefaultGenerator" );
	int n = 200;
	int neighbors = 15;

	boost::shared_ptr< IGraphOperation > operation( new GenBipartLinkNear() );

	DefaultGraphGenerator defGen( operation );
	IGraphGenerator * generator = & defGen;

	Graph gr;
	BOOST_CHECK_EQUAL( 0, gr.getVertexCount() );
	BOOST_CHECK_EQUAL( ( Graph::AdjMatrixType ) 0, gr.getAdjacentMatrixArr() );

	IOperationSettings oset( n );
	oset.neighborsBeg = neighbors;
	oset.neighborsRange = 1;
	generator->generateGraph( gr, oset );
	BOOST_CHECK_EQUAL( n, gr.getVertexCount() );
	assert( n == gr.getVertexCount() );

	for ( int i = 0; i < n; i++ )
	{
		int neighborCount = 0;
		for ( int j = 0; j < n; j++ )
		{
			if ( gr.existsEdge( i, j ) )
			{
				neighborCount++;
			}
		}
		BOOST_CHECK_GE( neighborCount, neighbors - neighbors / 3 );
		BOOST_CHECK_LE( neighborCount, neighbors * 2 );
		if ( neighborCount < neighbors - neighbors / 3 || neighborCount > neighbors * 2 )
		{
			std::cout << "\ni: " << i << " neighbors[expected]: " << neighbors << " neighborCount: " << neighborCount << "\n";
			assert( neighborCount >= neighbors - neighbors / 3 && neighborCount <= neighbors * 2 );
		}
	}
}

void edge2stream( std::ostream & buf, FacilitiesGraph & fgraph, int city, int facility )
{
	if ( fgraph.existsBiPartEdge( city, facility ) )
	{
		buf << fgraph.getFSEdge( city, facility );
	} else
	{
		buf << "INF";
	}
}

void compareGraphs( FacilitiesGraph & fgraphA, FacilitiesGraph & fgraphB, std::ostream & buf )
{
	double EPS = 1e-5;

	if ( fgraphA.getCitiesCount() != fgraphB.getCitiesCount() )
	{
		buf << "diff cities size: " << fgraphA.getCitiesCount() << " != " << fgraphB.getCitiesCount();
		return;
	}
	if ( fgraphA.getFacilitiesCount() != fgraphB.getFacilitiesCount() )
	{
		buf << "diff facilities size: " << fgraphA.getFacilitiesCount() << " != " << fgraphB.getFacilitiesCount();
		return;
	}

	int diffCount = 0;
	for ( int i = 0; i < fgraphA.getCitiesCount(); i++ )
	{
		for ( int j = 0; j < fgraphA.getFacilitiesCount(); j++ )
		{
			if ( std::abs( fgraphA.getFSEdge( i, j ) - fgraphB.getFSEdge( i, j ) ) > EPS )
			{
				buf << " diff edge: " << i << " -> " << j << " A: ";
				edge2stream( buf, fgraphA, i, j );
				buf << " B: ";
				edge2stream( buf, fgraphB, i, j );
				diffCount++;
			}
			if ( diffCount > 5 ) return;
		}
	}

	for ( int j = 0; j < fgraphA.getFacilitiesCount(); j++ )
	{
		if ( std::abs( fgraphA.facilitiesPrices[j] - fgraphB.facilitiesPrices[j] ) > EPS )
		{
			buf << " diff facilities prices [" << j << "]: " << fgraphA.facilitiesPrices[j]
				<< " != " << fgraphB.facilitiesPrices[j];
			diffCount++;
			if ( diffCount > 5 ) return;
		}
	}

	if ( diffCount == 0 )
	{
		buf << "Graphs are equal";
	}
}

std::string compareGraphs( FacilitiesGraph & fgraphA, FacilitiesGraph & fgraphB )
{
	std::stringstream buf;
	compareGraphs( fgraphA, fgraphB, buf );
	return buf.str();
}

void TestRandomSetupInGeneration()
{
//	IGNORE( "TestRandomSetupInGeneration" );
	CompoundGraphOperation * mainOp = new CompoundGraphOperation();
	IGraphOperationPtr mainOpPtr( mainOp );
	mainOp->addSubOperation( IGraphOperationPtr( new GenBipartLinkNear() ) );
	mainOp->addSubOperation( IGraphOperationPtr( new AddChpExpWeightsOperation() ) );
	mainOp->addSubOperation( IGraphOperationPtr( new MakeSymmOperation() ) );
	mainOp->addSubOperation( IGraphOperationPtr( new GeneratePricesOperation() ) );

	DefaultGraphGenerator * defGenerator = new DefaultGraphGenerator( mainOpPtr );
	IGraphGeneratorPtr generator( defGenerator );

	// ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###

	IOperationSettings genSettings( 100, 50 );
	genSettings.cheapRange = 1;
	genSettings.expensiveRange = 1;
	genSettings.facilityPriceRange = 1;

	FacilitiesGraph fgraphA;
	genSettings.setRandomSeed( 9876 );
	generator->generateGraph( fgraphA, genSettings );

	FacilitiesGraph fgraphB;
	genSettings.setRandomSeed( 9876 );
	generator->generateGraph( fgraphB, genSettings );

	BOOST_CHECK_EQUAL( std::string( "Graphs are equal" ), compareGraphs( fgraphA, fgraphB ) );

	// ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###

	genSettings.setRandomSeed( 12345 );
	generator->generateGraph( fgraphA, genSettings );

	genSettings.setRandomSeed( 67890 );
	generator->generateGraph( fgraphB, genSettings );


	BOOST_CHECK_EQUAL(
		std::string( " diff edge: 0 -> 1 A: 1.18286 B: INF" ) +
		std::string( " diff edge: 0 -> 9 A: INF B: 1.49985" ) +
		std::string( " diff edge: 1 -> 12 A: 1.66303 B: INF" ) +
		std::string( " diff edge: 1 -> 38 A: INF B: 1.71996" ) +
		std::string( " diff edge: 2 -> 7 A: 1.9543 B: INF" ) +
		std::string( " diff edge: 2 -> 23 A: INF B: 1.74321" ),
		compareGraphs( fgraphA, fgraphB )
	);
}

void TestTriangleInequalityCloseOperation()
{
	Graph::AdjCoefType EPS = 1e-5;

	int n = 10;
	BiGraph gr( n, 0 );

	Graph::AdjMatrixType adjMatr = gr.getAdjacentMatrixArr();

	adjMatr[0][1] = 1.0;
	adjMatr[1][2] = 2.0;
	adjMatr[2][3] = 3.0;
	adjMatr[0][3] = 100.0;

	BOOST_CHECK_GE( adjMatr[0][3], 100.0 - EPS );

	TriangleInequalityCloseOperation triaOp;
	IGraphOperation * operation = & triaOp;
	operation->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );

	BOOST_CHECK_LE( adjMatr[0][2], 3.0 + EPS );
	BOOST_CHECK_LE( adjMatr[2][3], 3.0 + EPS );
	BOOST_CHECK_LE( adjMatr[0][3], 6.0 + EPS );

	adjMatr[9][0] = 100;
	operation->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );
	for ( int i = 0; i < n; i++ )
	{
		BOOST_CHECK_LE( adjMatr[9][i], adjMatr[0][i] + 100 + EPS );
	}

	// ###
	n = 100;
	double eps = 1e-5;
	IGraphGeneratorPtr graphGenerator(
		new DefaultGraphGenerator(
			CompoundGraphOperation::createOperation(
				3,
				new GenBipartLinkNear(),
				new AddChpExpWeightsOperation(),
				new MakeSymmOperation()
			)
		)
	);
	IOperationSettings oset( n / 2, n - n / 2 );
	oset.neighborsBeg = 5;
	oset.neighborsRange = 10;
	graphGenerator->generateGraph( gr, oset );

	BOOST_CHECK_EQUAL( n, gr.getVertexCount() );
	adjMatr = gr.getAdjacentMatrixArr();
	int conflictsCount = 0;
	for ( int i = 0; i < n; i++ )
	{
		for ( int j = 0; j < n; j++ )
		{
			for ( int k = 0; k < n; k++ )
			{
				if ( adjMatr[i][j] > adjMatr[i][k] + adjMatr[k][j] + eps )
				{
					conflictsCount++;
				}
			}
		}
	}
	BOOST_CHECK_LT( 5000, conflictsCount ); // probabilistic evaluation

	operation->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );
	int conflictsCountB = 0;
	for ( int i = 0; i < n; i++ )
	{
		for ( int j = 0; j < n; j++ )
		{
			for ( int k = 0; k < n; k++ )
			{
				if ( adjMatr[i][j] > adjMatr[i][k] + adjMatr[k][j] + eps )
				{
					conflictsCountB++;
				}
			}
		}
	}
	BOOST_CHECK_EQUAL( 0, conflictsCountB );
}

void TestGenerateFacilityPrices()
{
	int expectedPriceBeg = 123;
	int priceRange = 45;
	GeneratePricesOperation gpop/*( expectedPriceBeg, priceRange )*/;
	IGraphOperation * grop = & gpop;

	Graph pureGraph( 123 );
	IOperationSettings getSettings;
	getSettings.facilityPriceBeg = expectedPriceBeg;
	getSettings.facilityPriceRange = priceRange;
	grop->applyTo( pureGraph, getSettings );
	for ( int i = 0; i < pureGraph.getVertexCount(); i++ )
	{
		for ( int j = 0; j < pureGraph.getVertexCount(); j++ )
		{
			BOOST_CHECK( !pureGraph.existsEdge( i, j ) );
		}
	}

	BiGraph biGraph( 23, 45 );
	grop->applyTo( pureGraph, getSettings );
	for ( int i = 0; i < biGraph.getFirstBipart(); i++ )
	{
		for ( int j = 0; j < biGraph.getSecondBipart(); j++ )
		{
			BOOST_CHECK( !biGraph.existsBiPartEdge( i, j ) );
		}
	}

	int citiesCount = 678;
	int facilitiesCount = 789;
	PrimDualSolvContext scontext;
	BOOST_CHECK( true );
	getSettings.firstBipart = citiesCount;
	getSettings.secondBipart = facilitiesCount;
	DefaultGraphGenerator(
		IGraphOperationPtr( new MakeSymmOperation() )
	).generateGraph( scontext.fgraph, getSettings );
	BOOST_CHECK( true );
	CRITICAL_CHECK( facilitiesCount == scontext.fgraph.getFacilitiesCount() );
	BOOST_CHECK( true );

	grop->applyTo( scontext.fgraph, getSettings );
	BOOST_CHECK( true );
	for ( int i = 0; i < scontext.fgraph.getFirstBipart(); i++ )
	{
		for ( int j = 0; j < scontext.fgraph.getSecondBipart(); j++ )
		{
			BOOST_CHECK( !scontext.fgraph.existsBiPartEdge( i, j ) );
		}
	}
	CRITICAL_CHECK( facilitiesCount == scontext.fgraph.facilitiesPrices.size() );
	FacilitiesGraph::FacilityPriceType sumPrice = 0;
	for ( int j = 0; j < scontext.fgraph.getFacilitiesCount(); j++ )
	{
		BOOST_CHECK_LT( scontext.fgraph.facilitiesPrices[j], scontext.fgraph.getInfEdge() - 1e20 );
		sumPrice += scontext.fgraph.facilitiesPrices[j];
	}
	FacilitiesGraph::FacilityPriceType avPrice = sumPrice / facilitiesCount;
	BOOST_CHECK_CLOSE( avPrice, expectedPriceBeg + priceRange / 2.0, 0.5 );
}

class FakeGraphOperation : public IGraphOperation
{
public:
	static int instanceCounter;

public:
	FakeGraphOperation( int pos, int val )
		: pos( pos )
		, val( val )
	{
		instanceCounter++;
	}

	~FakeGraphOperation()
	{
		instanceCounter--;
	}

	virtual void applyTo( Graph & graph, IOperationSettings & )
	{
		graph.getAdjacentMatrixArr()[0][pos] = val;
	}

private:
	int pos;
	int val;
};

int FakeGraphOperation::instanceCounter = 0;

void TestCompoundGraphOperation()
{
	int n = 10;
	Graph gr( n, 0 );
	Graph::AdjMatrixType adjMatr = gr.getAdjacentMatrixArr();

	BOOST_CHECK_EQUAL( std::string( "0, 0, 0, 0, 0, 0, 0, 0, 0, 0" ), ARR_TO_STRING( adjMatr[0], n ) );

	IGraphOperationPtr op = IGraphOperationPtr( new CompoundGraphOperation() );
	op->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );
	BOOST_CHECK_EQUAL( std::string( "0, 0, 0, 0, 0, 0, 0, 0, 0, 0" ), ARR_TO_STRING( adjMatr[0], n ) );

	op = CompoundGraphOperation::createOperation( 1, new FakeGraphOperation( 0, -1 ) );
	op->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );
	BOOST_CHECK_EQUAL( std::string( "-1, 0, 0, 0, 0, 0, 0, 0, 0, 0" ), ARR_TO_STRING( adjMatr[0], n ) );

	BOOST_CHECK_EQUAL( 1, FakeGraphOperation::instanceCounter );

	op = CompoundGraphOperation::createOperation(
		4,
		new FakeGraphOperation( 0, 123 ),
		new FakeGraphOperation( 1, 234 ),
		new FakeGraphOperation( 2, 345 ),
		new FakeGraphOperation( 3, 456 )
	);
	op->applyTo( gr, IOperationSettings::EMPTY_SETTINGS );
	BOOST_CHECK_EQUAL( std::string( "123, 234, 345, 456, 0, 0, 0, 0, 0, 0" ), ARR_TO_STRING( adjMatr[0], n ) );

	BOOST_CHECK_EQUAL( 4, FakeGraphOperation::instanceCounter );

	op = IGraphOperationPtr();

	BOOST_CHECK_EQUAL( 0, FakeGraphOperation::instanceCounter );
}
